// https://www.lintcode.com/problem/find-words/

public class Solution {
  /**
    * @param str: the string
    * @param dict: the dictionary
    * @return: return words which  are subsequences of the string
    */
  public List<String> findWords(String str, List<String> dict) {
    // Write your code here.
    List<String> ret = new ArrayList<>();
    Map<Character, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < str.length(); ++i) {
      Character c = str.charAt(i);
      if (!map.containsKey(c)) {
        map.put(c, new ArrayList<>());
      }
      map.get(c).add(i);
    }
    for (String word : dict) {
      int minPos = -1;
      boolean isMatch = true;
      for (int i = 0; i < word.length(); ++i) {
        Character c = word.charAt(i);
        if (!map.containsKey(c)) {
          isMatch = false;
          break;
        }
        int j = 0;
        while (j < map.get(c).size()) {
          if (map.get(c).get(j) > minPos) {
            minPos = map.get(c).get(j);
            break;
          }
          ++j;
        }
        if (j == map.get(c).size()) {
          isMatch = false;
          break;
        }
      }
      if (isMatch) {
        ret.add(word);
      }
    }
    return ret;
  }
}